//
//  main.c
//  chuan串-朴素的模式匹配算法
//
//  Created by Song on 2018/3/13.
//  Copyright © 2018年 Song. All rights reserved.
//

// 自写

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 求字符串长度函数
int strlen1(char *s){
    int n;
    for(n=0;s[n]!='\0';n++);
    return n;
}

int doIndex(char s[], char t[]) { // 将 目标串S 的第?个字符与 模式串T 的第?个字符进行匹配
    
//    int flag;
    int flag = 0;
    
    int i = 0,j = 0;
    
    int lenS, lenT;
    lenS = strlen1(s);
    lenT = strlen1(t);
    
    int temp;
    
    for (temp = 0; temp < lenS; temp++) { // 第一个 for 循环
        /*
             性能上有多余：
             eg：s = abcd；  (i)
                 t = cde；  (j)
             当s的c、d，分别与t的c、d比较完毕并相等后，s/i 已经是最后一个了，但是t/j还剩一个元素，即此时：i=3,j=1,temp=2，就会进入到下文井号“#”的位置，j++，j=2，t/j到达最后一个。
             因为i已经是最后了，所以会跳出第二个for循环,此时temp加一,temp=3,i=3,j=2，然后进入第二个for循环，相当于s[3]与t[2]进行了一次比较（但是在之前s[3]已经参与过比较），所以会有多余的判断。
         */
        
//        i = temp;
        
        // i = temp， 用来让s所对应的i回到上次进入循环的下一个元素的位置
        for (i  = temp; i < lenS; i++) { // s 即对应 i， t对应j  ，第二个for循环
            if (s[i] == t[j]) { // 1.如果s[i] == t[j]
                
                if (j == lenT -1) { // 判断j，即t是不是已经到了最后，如果t已经到了最后全部判断完毕，又在相等的条件下，说明t是子串，返回1
                    flag = 1;
                    return 1;
                    break;
                }
                j++; // 判断 j 并不是最后的，所以需要加一，然后continue，去下一遍循环里判断j与i都加一以后，是否还相等
                continue;
            }else if (i == lenS-1) { // 如果 i 已经是s的最后一个了
                if (j == lenT -1) { //  j 已经是t的最后一个
                    flag = 0;
                    return 0; // 不是子串
                    break;
                }
                j++; // ############## 会产生多余的判断 ##############
                continue;
            }else {
                j = 0; // 继续用t的第一个位置（j=0）的元素去跟i+1(temp也加一)之后的元素判断
                break;
            }
        }
        
        
    }

    return flag;
}

int main(int argc, const char * argv[]) {
    
//    int temp;
//    char s[]= "123456";
//    temp = strlen1(s);
//    printf("%d\n",temp);

    char s[] = "abcd";
    char t[] = "bcw";
    
//    char s[] = "ababcababaw";
//    char t[] = "ababcababw"; // abab
    
//    char s[] = "0000000000001";
//    char t[] = "00001";

    int flag1;
    
    flag1 = doIndex(s, t);
    
    if (flag1 == 1) {
        printf("含有子串\n");
    }else {
        printf("flag1 = %d \n",flag1);
        printf("不含\n");
    }
    
    return 0;
}


